/** 52
 * @param {number} n
 * @return {number}
 */
 var totalNQueens = function(n) {
    let board=new Array(n).fill(0).map(() => new Array(n).fill(0));
    let ret=0;
    function insertQ(x,y,val){
        for(let i=0;i<n;i++){
            board[x][i]+=val;
            board[i][y]+=val;
        }
        let i=1;
        while(x-i>=0&&y-i>=0){
            board[x-i][y-i]+=val;
            i++;
        }
        i=1;
        while(x+i<n&&y+i<n){
            board[x+i][y+i]+=val;
            i++;
        }
        i=1;
        while(x-i>=0&&y+i<n){
            board[x-i][y+i]+=val;
            i++;
        }
        i=1;
        while(x+i<n&&y-i>=0){
            board[x+i][y-i]+=val;
            i++;
        }
    }
    function findS(x){
        if(x===n){
            ret++;
            return ;
        }
        for(let i=0;i<n;i++){
            if(!board[x][i]){
                insertQ(x,i,1);
                findS(x+1);
                insertQ(x,i,-1);
            }
        }
    }
    findS(0);
    return ret;
};

// 执行用时：
// 116 ms
// , 在所有 JavaScript 提交中击败了
// 13.33%
// 的用户
// 内存消耗：
// 40.1 MB
// , 在所有 JavaScript 提交中击败了
// 24.55%
// 的用户